package avltree;


public class AVLTree {
    static class TreeNode {
        public int val;
        public int bf; //平衡因子 -- balance factor
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;  //父亲节点的引用

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root; //根节点

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }

        //cur = null
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        //
        node.parent = parent;
        cur = node;
        //平衡因子的修改
        while (parent != null) {
            //先看cur是parent的左还是右, 决定平衡因子是++还是--
            if (cur == parent.right) {
                //如果是右树,那么右树高度增加, 平衡因子++
                parent.bf++;
            } else {
                //如果是左树,那么右树高度增加, 平衡因子--
                parent.bf--;
            }

            //检查当前的平衡因子是不是绝对值<1
            if(parent.bf == 0) {
                //说明已经平衡了
                break;
            }else if(parent.bf == 1 || parent.bf == -1) {
                //继续向上去修改平衡因子
                cur =parent;
                parent = cur.parent;
            }else {
                if(parent.bf == 2) { //右树高, 需要降低右树的高度
                    if(cur.bf == 1) {
                        //左旋
                        rotateLeft(parent);
                    }else {
                        // parent.bf == -1
                        //右左双旋
                        rotateRL(parent);
                    }
                } else {
                    //parent.bf == -2 左树高, 需要降低左树的高度
                    if(cur.bf == -1) {
                        //右旋
                        rotateRight(parent);
                    } else {
                        //cur.bf == 1
                        //左右双旋
                        rotateLR(parent);
                    }
                }
                //上述代码走完就平衡了
                break;
            }
        }

        return true;
    }

    //右左双旋
    private void rotateRL(TreeNode parent) {

    }

    //左右双旋
    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        int bf = subLR.bf;

        rotateLeft(parent.left);
        rotateRight(parent);

        if(bf == -1) {
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        }else {
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }

    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;

        parent.left = subLR;
        subL.right = parent;

        //没有subLR
        if(subLR != null) {
            subLR.parent = parent;
        }

        //必须先记录
        TreeNode pParent = parent.parent;
        parent.parent = subL;

        //检查当前是不是根节点
        if(parent == root) {
            root = subL;
        } else {
            //不是根节点, 判断这颗子树是左子树还是右子树
            if(pParent.left == parent) {
                pParent.left = subL;
            } else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }

        subL.bf = 0;
        parent.bf = 0;
    }

    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        parent.right = subRL;
        subR.left = parent;
        if(subRL!=null) {
            subRL.parent = parent;
        }

        TreeNode pParent = parent.parent;
        parent.parent = subR;

        if(root == parent) {
            root = subR;
            root.parent = null;
        }else {
            if(pParent.left == parent) {
                pParent.left = subR;
            }else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }

        subR.bf = parent.bf = 0;
    }
}
